package com.leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 322. 零钱兑换
 *
 * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成
 * 总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
 *
 * 你可以认为每种硬币的数量是无限的。
 * 示例 1：
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 */
public class Leet322 {
	public static void main(String[] args) {
//		System.out.println(new Leet322().coinChange(new int[]{1, 2,5}, 11));
		System.out.println(new Leet322().coinChange(new int[]{1, 7, 10}, 14));
//		System.out.println(new Leet322().coinChange(new int[]{186,419,83,408}, 6249));
//		System.out.println(new Leet322().coinChange(new int[]{186,419,83,408}, 419));
	}

	public int coinChange(int[] coins, int amount) {
		if (coins == null || coins.length == 0) return -1;
		if (coins.length == 1) return amount % coins[0] == 0 ? amount / coins[0] : -1;

		Arrays.sort(coins);
		backTrace2(coins, amount, coins.length - 1, 0);
		return countRes;
	}

	/**
	 * 别人:
	 * 学到了:利用栈帧的局部变量接收count,在合适的时候把count赋给countRes,省去对count的回溯.
	 * 学到了:要理解选择列表才能写出正确的
	 */
	public void backTrace2(int[] coins, int amount, int index, int count) {
		if (amount == 0) {
			countRes = countRes == -1 ? count : Math.min(count, countRes);
			return;
		}
//		if (amount < 0) return;
		if (index < 0) return;

		int i = amount / coins[index];
		for (int a = i; a >= 0&&(countRes==-1?true: a+count<countRes); a--) {//0.选择列表如何写?他的这种写法太妙了
//		for (int a = i; a >= 0; a--) {//0.选择列表如何写?他的这种写法太妙了
//			if (countRes != -1 && (a + count) >= countRes) {
//				continue;//把下面recur理解为"新开分支",而这筛选就是"剪枝",但480ms,剪枝写在for里面是4ms?!!
//			}
			/**
			 * 因为上面i可能为0,所以下面amount不变,index接着减1递归,太妙了
			 */
			backTrace2(coins, amount - a * coins[index], index - 1, count + a);
		}
	}

	int count = 0;
	int countRes = -1;
	boolean flag;
	List<Integer> l = new ArrayList();
	List<Integer> lRes;

	/**
	 * 总结:我下面写的是backTrace也可以叫作"贪心",得到是不一定是最优解.
	 * 回溯的对象是count,意味着count最后永远为0
	 * 方法的返回不应该是count,而是"接着recur" "中止"
	 * 考点:backTrace的return并不会提前结束整个"求解过程",return只是简单的弹栈而已.
	 * 大bug:最先解不一定是最优解,如1,7,10,找14,10,1,1,1比7,7快
	 */
	public void backTrace(int[] coins, int amount) {
		if (flag) return;
		if (amount == 0) {
			countRes = count;
			lRes = new ArrayList(l);
			flag = true;
			return;//4.bug2:
		}
		if (amount < coins[0]) return;

		for (int a = coins.length - 1; a >= 0; a--) {//5.bug3:选择列表不可能永远有n个选项,少传了参数b
			count++;//1.dosomething
			l.add(coins[a]);
			backTrace(coins, amount - coins[a]);//2.recur,bug1:a写成nums.length-1
			count--;//3.backTrace
			l.remove(l.size() - 1);
		}
	}

}
